﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _04_Graph
{
   class Graph
   {
      // 点集
      public Dictionary<int, Node> nodes;
      // 边集
      public HashSet<Edge> edges;

      public Graph()
      {
         this.nodes = new Dictionary<int, Node>();
         this.edges = new HashSet<Edge>();
      }

      // 三元组 转 邻接表
      public static Graph Parse(int[][] matrix)
      {
         Graph res = new Graph();

         for (int i = 0; i < matrix.Length; i++)
         {
            int from = matrix[i][1];
            int to = matrix[i][2];
            int weight = matrix[i][0];

            // 生成点
            if (!res.nodes.ContainsKey(from))
               res.nodes.Add(from, new Node(from));
            if (!res.nodes.ContainsKey(to))
               res.nodes.Add(to, new Node(to));

            // 生成边
            Node fromNode = res.nodes[from];
            Node toNode = res.nodes[to];
            Edge edge = new Edge(weight, fromNode, toNode);
            res.edges.Add(edge);

            // 调整点间关系
            fromNode.m_out++;
            toNode.m_in++;
            fromNode.nexts.Add(toNode);
            fromNode.edges.Add(edge);
         }

         return res;
      }

      // 邻接矩阵 转 邻接表
      public static Graph Parse(int[] nodes, int[][] edges)
      {
         Graph res = new Graph();

         // 构建点集
         for (int i = 0; i < nodes.Length; i++)
            res.nodes.Add(i, new Node(nodes[i]));

         // 构建边集
         for (int i = 0; i < edges.Length; i++)
         {
            for (int j = 0; j < edges[i].Length; j++)
            {
               if (edges[i][j] != int.MinValue)
               {
                  Node fromNode = res.nodes[i];
                  Node toNode = res.nodes[j];
                  Edge edge = new Edge(edges[i][j], fromNode, toNode);
                  res.edges.Add(edge);
                  // 更新关系
                  fromNode.m_out++;
                  fromNode.edges.Add(edge);
                  fromNode.nexts.Add(toNode);
                  toNode.m_in++;
               }
            }
         }

         return res;
      }

      // BFS
      public static void BFS(Node node, Action<int> action)
      {
         if (node == null)
            return;
         Queue<Node> queue = new Queue<Node>();
         HashSet<Node> record = new HashSet<Node>();
         queue.Enqueue(node);
         record.Add(node);
         Node cur;
         while (queue.Count != 0)
         {
            cur = queue.Dequeue();
            action.Invoke(cur.value);
            foreach (var item in cur.nexts)
            {
               if (!record.Contains(item))
               {
                  queue.Enqueue(item);
                  record.Add(item);
               }
            }
         }
      }

      // DFS 递归
      private static void _DFS_Recursive_Process(Node node, HashSet<Node> record, Action<int> action)
      {
         if (node == null || record.Contains(node))
            return;
         action.Invoke(node.value);
         record.Add(node);
         foreach (var item in node.nexts)
         {
            _DFS_Recursive_Process(item, record, action);
         }
      }
      public static void DFS_Recursive(Node node, Action<int> action)
      {
         HashSet<Node> record = new HashSet<Node>();
         _DFS_Recursive_Process(node, record, action);
      }

      // DFS 非递归
      public static void DFS(Node node, Action<int> action)
      {
         if (node == null)
            return;
         Stack<Node> stack = new Stack<Node>();
         HashSet<Node> record = new HashSet<Node>();
         stack.Push(node);
         record.Add(node);
         action.Invoke(node.value);
         Node cur;
         while (stack.Count != 0)
         {
            cur = stack.Pop();
            foreach (var item in cur.nexts)
            {
               if (!record.Contains(item))
               {
                  stack.Push(cur);  // 把出栈的cur先压回去
                  stack.Push(item);
                  action.Invoke(item.value);
                  record.Add(item);
                  break;
               }
            }
         }
      }

      // 拓扑排序
      public static List<Node> TopologicalSort(Graph g)
      {
         // 记录 结点->入度 的信息
         Dictionary<Node, int> nodeIn = new Dictionary<Node, int>();
         // 存储入度为0的结点
         Queue<Node> zeroIn = new Queue<Node>();
         // 存储拓扑排序的结果
         List<Node> res = new List<Node>();

         // 初始化nodeIn和zeroIn
         foreach (var node in g.nodes.Values)
         {
            nodeIn.Add(node, node.m_in);
            if (node.m_in == 0)
               zeroIn.Enqueue(node);
         }

         while (zeroIn.Count != 0)
         {
            Node cur = zeroIn.Dequeue();
            res.Add(cur);
            // 更新入度表和零入度队列的数据
            foreach (var node in cur.nexts)
            {
               nodeIn[node]--;
               if (nodeIn[node] == 0)
                  zeroIn.Enqueue(node);
            }
         }

         return res;
      }

      // K算法
      public static List<Edge> Kruskal(Graph g)
      {
         // 构建并查集
         UnionFind unionFind = new UnionFind(g.nodes.Values.ToList());
         // 构建有序的边集
         SortedSet<Edge> edges = new SortedSet<Edge>();
         foreach (var edge in g.edges)
            edges.Add(edge);

         List<Edge> res = new List<Edge>();
         while (edges.Count != 0)
         {
            // 取最小边
            Edge minEdge = edges.Min;
            edges.Remove(minEdge);
            // 判断是否在同一集合
            if (!unionFind.IsSameSet(minEdge.from, minEdge.to))
            {
               res.Add(minEdge);
               unionFind.Union(minEdge.from, minEdge.to);
            }
         }

         return res;
      }

      // P算法
      public static List<Edge> Prim(Graph g)
      {
         // 解锁边集合
         SortedSet<Edge> availableEdges = new SortedSet<Edge>();
         // 记录已经访问的结点
         HashSet<Node> nodeRecord = new HashSet<Node>();
         // 结果 最小生成树
         List<Edge> res = new List<Edge>();

         foreach (var node in g.nodes.Values.ToList())
         {
            if (!nodeRecord.Contains(node))
            {
               nodeRecord.Add(node);   // 生成该点的记录
               // 解锁邻接边
               foreach (var edge in node.edges)
                  availableEdges.Add(edge);
               while (availableEdges.Count != 0)
               {
                  Edge minEdge = availableEdges.Min;
                  availableEdges.Remove(minEdge);
                  Node toNode = minEdge.to;
                  // 新边
                  if (!nodeRecord.Contains(toNode))
                  {
                     nodeRecord.Add(toNode);
                     res.Add(minEdge);
                     foreach (var nextEdge in toNode.edges)
                        availableEdges.Add(nextEdge);
                  }
               }
            }
         }

         return res;
      }

      // D算法
      private static Node _DA_GetNode(Dictionary<Node, int> disMap, HashSet<Node> record)
      {
         Node minNode = null;
         int minDis = int.MaxValue;
         foreach (KeyValuePair<Node, int> pair in disMap)
         {
            if (!record.Contains(pair.Key))
            {
               minNode = (minDis > pair.Value) ? pair.Key : minNode;
               minDis = (minDis > pair.Value) ? pair.Value : minDis;
            }
         }

         return minNode;
      }
      public static Dictionary<Node, int> Dijkstra(Node head)
      {
         // 最短路径表
         Dictionary<Node, int> disMap = new Dictionary<Node, int>();
         disMap.Add(head, 0); // 有记录表示最短路径，无记录表示无路径
         // 访问结点记录
         HashSet<Node> record = new HashSet<Node>();
         Node minNode = _DA_GetNode(disMap, record);

         while (minNode != null)
         {
            int dis = disMap[minNode];
            // 更新最短路径表
            foreach (var edge in minNode.edges)
            {
               Node toNode = edge.to;
               if (!disMap.ContainsKey(toNode))
                  disMap.Add(toNode, dis + edge.weight);
               disMap[toNode] = (disMap[toNode] > (dis + edge.weight)) ?
                  dis + edge.weight : disMap[toNode];
            }
            // 添加记录
            record.Add(minNode);
            minNode = _DA_GetNode(disMap, record);
         }

         return disMap;
      }
   }
}
